import random
from copy import deepcopy
from TSP import TSP
import matplotlib.pyplot as plt


def nearest_neighbor(distance_matrix):
    """ return the cost of route constructing by the nearest neighbor heuristic """
    route = [random.randint(0, len(distance_matrix) - 2)]
    unvisited = list(range(len(distance_matrix) - 1))
    unvisited.remove(route[0])
    while unvisited:
        target, min_dis = -1, 1e99
        for city in unvisited:
            if min_dis > distance_matrix[route[-1] + 1][city + 1]:
                min_dis = distance_matrix[route[-1] + 1][city + 1]
                target = city
        route.append(target)
        unvisited.remove(target)
    return route


def caculatedistance(distance_matrix, order):
    distancesum = 0.0
    for num in range(len(order)):
        distancesum += distance_matrix[order[num] + 1, order[(num + 1) % (len(order))] + 1]
    return distancesum


def removeall(a, e):
    b = []
    for ee in a:
        if ee not in e:
            b.append(ee)
        else:
            continue
    return b


def edgestoroute(edges):
    route, belongs = [], []
    while len(edges) > 0:
        belongs.append(edges[0][-1])
        route.append(edges[0][0:2])
        edges.remove(edges[0])
        while route[-1][-1] != route[-1][0]:
            for edge in edges:
                if route[-1][-1] in edge:
                    route[-1].append(edge[1 - edge.index(route[-1][-1])])
                    edges.remove(edge)
                    break
    for i in range(len(route)):
        route[i] = [route[i][0:len(route[i]) - 1], belongs[i]]
    return route


def edgestoABroute(edges):  # 比edgestoroute增加判断边交替来自P1和P2的过程
    route, belongs = [], []
    while len(edges) > 0:
        flag = 1 if edges[0][-1] == 'p1' else 0  # flag：下一条边。 0 means p1 and 1 means p2
        belongs.append(edges[0][-1])
        route.append(edges[0][0:2])
        edges.remove(edges[0])
        while route[-1][-1] != route[-1][0] or (len(route[-1]) % 2 == 0):
            for edge in edges:
                if route[-1][-1] in edge and ((edge[-1] == 'p1') ^ flag):
                    route[-1].append(edge[1 - edge.index(route[-1][-1])])
                    edges.remove(edge)
                    flag = 1 - flag
                    break
    for i in range(len(route)):
        route[i] = [route[i][0:len(route[i]) - 1], belongs[i]]  # belongs表示route中第一条边的归属
    return route


def routetoedges(routes):
    edges = []
    for route in routes:
        for i in range(len(route[0])):
            if route[-1] == 'p1':
                belongs = 'p2' if i % 2 else 'p1'
            else:
                belongs = 'p1' if i % 2 else 'p2'
            edges.append([route[0][i], route[0][(i + 1) % len(route[0])], belongs])
    return edges


def decreasecircle(matrix, circle):  # step5
    rk = [caculatedistance(matrix, i) for i in circle]
    rk = circle[rk.index(min(rk))]
    circle.remove(rk)
    besta, bestb, bestroute = 0, 0, 0
    best = matrix[rk[0] + 1][rk[1] + 1] + matrix[circle[0][0] + 1][circle[0][1] + 1] - \
           matrix[rk[0] + 1][circle[0][0] + 1] - matrix[rk[1] + 1][circle[0][1] + 1]
    pflag = 0
    for a in range(len(rk)):
        for route in range(len(circle)):
            for b in range(len(circle[route])):
                temp = matrix[rk[a] + 1][rk[(a + 1) % len(rk)] + 1] + \
                       matrix[circle[route][b] + 1][circle[route][(b + 1) % len(circle[route])] + 1] - \
                       matrix[rk[a] + 1][circle[route][b] + 1] - \
                       matrix[rk[(a + 1) % len(rk)] + 1][
                           circle[route][(b + 1) % len(circle[route])] + 1]
                if temp > best:
                    best, besta, bestb, bestroute = temp, a, b, route
    rk = rk[::-1]
    for a in range(len(rk)):
        for route in range(len(circle)):
            for b in range(len(circle[route])):
                temp = matrix[rk[a]][rk[(a + 1) % len(rk)]] + \
                       matrix[circle[route][b]][circle[route][(b + 1) % len(circle[route])]] - \
                       matrix[rk[a]][circle[route][b]] - \
                       matrix[rk[(a + 1) % len(rk)]][circle[route][(b + 1) % len(circle[route])]]
                if temp > best:
                    pflag = 1
                    best, besta, bestb, bestroute = temp, a, b, route
    if not pflag:
        rk = rk[::-1]
    rk = rk[besta + 1:] + rk[:besta + 1] if (besta + 1) % len(rk) else rk
    circle[bestroute] = circle[bestroute][bestb + 1:] + circle[bestroute][:bestb + 1] \
        if (bestb + 1) % len(circle[bestroute]) else circle[bestroute]
    circle[bestroute] = circle[bestroute] + rk[::-1]
    return circle


def EAX(matrix, parent1, parent2):
    genelength = len(parent1)
    choice = random.randint(0, genelength - 1)
    parent1 = parent1[parent1.index(choice):] + parent1[:parent1.index(choice)]
    parent2 = parent2[parent2.index(choice):] + parent2[:parent2.index(choice)]
    edge1 = [[parent1[i], parent1[(i + 1) % genelength], 'p1'] for i in range(genelength)]
    edge2 = [[parent2[i], parent2[(i + 1) % genelength], 'p2'] for i in range(genelength)]
    Aset, Bset = [], []
    for i in range(genelength):
        if i % 2:
            Bset.append(edge1[i])
            Bset.append(edge2[i])
        else:
            Aset.append(edge1[i])
            Aset.append(edge2[i])
    ABset = edgestoABroute(Aset) + edgestoABroute(Bset)
    for i in ABset:
        if len(i)%2==1:
            print(exit(0))
    Eset = removeall([i if len(i[0]) > 2 and random.random() > 0.5 else [] for i in ABset], [[]])

    Esetedges = routetoedges(Eset)
    offedge1, offedge2 = deepcopy(edge1), deepcopy(edge2)
    for edge in Esetedges:
        if edge[-1] == 'p1':
            if edge in offedge1:
                offedge1.remove(edge)
            else:
                offedge1.remove(edge[0:2][::-1] + [edge[-1]])
            offedge2.append(edge)
        else:
            if edge in offedge2:
                offedge2.remove(edge)
            else:
                offedge2.remove(edge[0:2][::-1] + [edge[-1]])
            offedge1.append(edge)
    offedge1, offedge2 = edgestoroute(offedge1), edgestoroute(offedge2)
    off = [[i[0] for i in offedge1], [i[0] for i in offedge2]]
    for num in range(len(off)):
        while len(off[num]) > 1:
            off[num] = decreasecircle(matrix, off[num])
    return off[0][0], off[1][0], Eset


case = 'bays29'
tsp_data = TSP(path=f'../../data/TSPLIB/{case}.tsp.txt')
genelength = tsp_data.n
Distance = tsp_data.distance_matrix
parent = [nearest_neighbor(Distance), nearest_neighbor(Distance)]
for i in range(1000):
    print(i + 1, '次')
    for num in range(2):
        print(parent[num])
    child1, child2, Eset = EAX(Distance, parent[0], parent[1])
    child = [child1, child2]
    for num in range(2):
        print(child[num])
    if len(child1) != len(child2):
        exit(0)

fig = plt.figure()
for position in range(len(parent[0])):
    for num in range(2):
        parent[num][position] += 1
        child[num][position] += 1
for num in range(2):
    plt.subplot(3, 2, num + 1)
    # plt.gca().add_patch(plt.Rectangle(start_point, Lx, Ly, color='forestgreen', fill=False))
    parent[num].append(parent[num][0])
    tsp_data.draw(plt, route=parent[num], show_text=False)
    plt.title('parent' + str(num + 1))

for num in range(2):
    plt.subplot(3, 2, num + 3)
    # plt.gca().add_patch(plt.Rectangle(start_point, Lx, Ly, color='forestgreen', fill=False))
    child[num].append(child[num][0])
    tsp_data.draw(plt, route=child[num], show_text=False)
    plt.title('child' + str(num + 1))
for num in range(2):
    plt.subplot(3, 2, 5)
    print('Eset', Eset)
    for route in Eset:
        route = [i + 1 for i in route[0]]
        route.append(route[0])
        tsp_data.draw(plt, route=route, show_text=False)
        
# plt.savefig('sample.svg')
plt.show()
